class Trie:
    def __init__(self):
        self.nodes = {}
        self.is_word = False

    def insert(self, word):
        if not word:
            self.is_word = True
        else:
            if word[0] not in self.nodes:
                self.nodes[word[0]] = Trie()
            self.nodes[word[0]].insert(word[1:])

    def search(self, word):
        if not word:
            return self.is_word
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].search(word[1:])

    def starts_with(self, word):
        if not word:
            return True
        elif word[0] not in self.nodes:
            return False
        else:
            return self.nodes[word[0]].starts_with(word[1:])


def search_words(board, words):
    trie = Trie()
    m = len(board)
    n = len(board[0])
    for word in words:
        trie.insert(word)

    def dfs(prefix, i, j):
        if i < 0 or j < 0 or i >= m or j >= n or not trie.starts_with(prefix + board[i][j]):
            return
        cur = prefix + board[i][j]
        visited.add((i, j))
        if trie.search(cur):
            result.add(cur)
        dfs(cur, i - 1, j)
        dfs(cur, i + 1, j)
        dfs(cur, i, j - 1)
        dfs(cur, i, j + 1)

    result = set()

    for i in range(m):
        for j in range(n):
            visited = set()
            dfs("", i, j)

    return list(result)


words = ["oath", "pea", "eat", "rain"]
board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
]
print(search_words(board, words))
